/**
 * Universidad Del Valle De Guatemala.
 * Algoritmos y Estructuras de Datos.
 * Sección 20.
 * Miguel Enrique Zea Arenales.
 * Carné 09238.
 * 20/09/2012.
 */
package heapshuffman;

/**
 * @author Miguel Zea
 * Implementación de una cola de prioridad mediante Skew Heaps.
 * Tomado del texto Java Structures de Duane A. Bailey capítulo 13.
 * http://www.cs.williams.edu/JavaStructures/Book.html
 */
public class PriorityQueueSkewHeap<E extends Comparable<E>> implements PriorityQueue<E> {
    protected BinaryTree<E> root; // Raíz del Heap.
    protected final BinaryTree<E> EMPTY = new BinaryTree<E>();
    protected int count; // Número de nodos contenidos en la cola.

    /**
     * @pre Ninguna.
     * @post Crea una cola con prioridad vacía.
     */
    public PriorityQueueSkewHeap() {
        root = EMPTY;
        count = 0;
    }

    /**
     * @pre La cola no está vacía.
     * @post Regresa el valor mínimo de la cola con prioridad.
     */
    @Override
    public E getFirst() {
        return root.value();
    }

    /**
     * @pre La cola no está vacía.
     * @post Regresa y elimina el valor mínimo de la cola con prioridad.
     */
    @Override
    public E remove() {
        E result = root.value();
        root = merge(root.left(), root.right());
        count--;
        return result;  
    }

    /**
     * @pre El valor es comparable y no nulo.
     * @post El valor se agrega a la cola con prioridad.
     */
    @Override
    public void add(E value) {
        BinaryTree<E> smallTree = new BinaryTree<E>(value, EMPTY, EMPTY);
        root = merge(smallTree, root);
        count++;
    }
    
    /**
     * @pre Ninguna.
     * @post Regresa verdadero si y sólo si no hay elementos en la cola.
     */
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * @pre Ninguna.
     * @post Regresa el número de elementos en la cola.
     */
    @Override
    public int size() {
        return count;
    }

    /**
     * @pre Ninguna.
     * @post Elimina todos los elementos de la cola.
     */
    @Override
    public void clear() {
        root = EMPTY;
    }

    /**
     * @pre Left y Right son heaps.
     * @post Combina dos heaps y retorna el resultante.
     */
    protected static <E extends Comparable<E>> BinaryTree<E> merge(BinaryTree<E> left, BinaryTree<E> right) {
        if (left.isEmpty()) return right;
        if (right.isEmpty()) return left;
        E leftVal = left.value();
        E rightVal = right.value();
        BinaryTree<E> result;
        if (rightVal.compareTo(leftVal) < 0) {
            result = merge(right, left);
        } else {
            result = left;
            // El nodo izquierdo es menor que el derecho.
            // El nodo izquierdo es la nueva raíz.
            if (result.left().isEmpty()) {
                result.setLeft(right);
            } else {
                BinaryTree<E> temp = result.right();
                result.setRight(result.left());
                result.setLeft(merge(temp, right));
            }
        }
        return result;
    }

}
